//<p>给你两个正整数&nbsp;<code>n</code> 和&nbsp;<code>limit</code>&nbsp;。</p>
//
//<p>请你将 <code>n</code>&nbsp;颗糖果分给 <code>3</code>&nbsp;位小朋友，确保没有任何小朋友得到超过 <code>limit</code>&nbsp;颗糖果，请你返回满足此条件下的&nbsp;<strong>总方案数</strong>&nbsp;。</p>
//
//<p>&nbsp;</p>
//
//<p><strong class="example">示例 1：</strong></p>
//
//<pre>
//<b>输入：</b>n = 5, limit = 2
//<b>输出：</b>3
//<b>解释：</b>总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。
//</pre>
//
//<p><strong class="example">示例 2：</strong></p>
//
//<pre>
//<b>输入：</b>n = 3, limit = 3
//<b>输出：</b>10
//<b>解释：</b>总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>1 &lt;= n &lt;= 50</code></li> 
// <li><code>1 &lt;= limit &lt;= 50</code></li> 
//</ul>
//
//<div><li>👍 8</li><li>👎 0</li></div>

#include <bits/stdc++.h>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int distributeCandies(int n, int limit) {
        vector cache(n + 1, vector<int>(3, -1));
        return backTrace(n, limit, 0, 3, cache);
    }

    /**
     *
     * @param n 剩余的糖果
     * @param limit 单人最多分的糖果
     * @param cur 当前已经分配了多少人
     * @param all 总共有多少人
     * @param cache 记忆化搜索缓存
     */
    int backTrace(int n, int limit, int cur, int all, vector<vector<int>>& cache) {
        if (cur == all) {
            return n == 0 ? 1 : 0;
        }
        if (cache[n][cur] >= 0) return cache[n][cur];
        int res = 0;
        // 当前至少要分配
        int s = max(0, n - (all - cur - 1) * limit);
        // 当前最多分配
        int t = min(n, limit);
        for (int i = s; i <= t; i++) {
            res += backTrace(n - i, limit, cur + 1, all, cache);
        }
        cache[n][cur] = res;
        return res;
    }
};

//leetcode submit region end(Prohibit modification and deletion)


int main() {
    Solution s;
    auto ans = s.distributeCandies(48, 48);
    cout << ans << endl;
}
